package com.hooper.solution.day2;

/**
 * @author Tim Hooper
 * @version 1.0
 * @time 2023/01/29/00:05
 */
public class Solutions {

    /**
     * 面试题 01.09. 字符串轮转
     * 字符串轮转。给定两个字符串s1和s2，请编写代码检查s2是否为s1旋转而成（比如，waterbottle是erbottlewat旋转后的字符串）。
     * 示例1:
     * 输入：s1 = "waterbottle", s2 = "erbottlewat"
     * 输出：True
     * 示例2:
     * 输入：s1 = "aa", s2 = "aba"
     * 输出：False
     */
    public boolean isFlipedString(String s1, String s2) {
        if (s1.length() != s2.length()) return false;
        //思路：
        //若一个字符是由另一个字符旋转而来
        //那其自身的两倍必定含有另一个字符
        //如 abcd 与 cdad
        //abcd -> abcdabcd 中含有 abcd,bcda,cdab,dabc
        return (s1 + s1).contains(s2);
    }


    /**
     * 给定两个整型数字 N 与 M，以及表示比特位置的 i 与 j（i <= j，且从 0 位开始计算）。
     * 编写一种方法，使 M 对应的二进制数字插入 N 对应的二进制数字的第 i ~ j 位区域，不足之处用 0 补齐。具体插入过程如图所示。
     * 题目保证从 i 位到 j 位足以容纳 M， 例如： M = 10011，则 i～j 区域至少可容纳 5 位。
     * 示例1:
     * 输入：N = 1024(10000000000), M = 19(10011), i = 2, j = 6
     * 输出：N = 1100(10001001100)
     * 示例2:
     * 输入： N = 0, M = 31(11111), i = 0, j = 4
     * 输出：N = 31(11111)
     **/
    public static int insertBits(int N, int M, int i, int j) {
        String n = Integer.toBinaryString(N);
        String m = Integer.toBinaryString(M);
        StringBuilder sb = new StringBuilder();
        for (int x = 0; x < n.length() - j - 1; x++) {
            sb.append(n.charAt(x));
        }
        int len = j - i + 1;
        StringBuilder builder = new StringBuilder(len);
        int mLen = m.length();
        while (mLen < len) {
            builder.append('0');
            mLen++;
        }
        sb.append(builder).append(m);
        for (int x = n.length() - i; x < n.length(); x++) {
            sb.append(n.charAt(x));
        }
        return Integer.parseInt(sb.toString(), 2);
    }

    /**
     * 面试题 10.01. 合并排序的数组
     * 给定两个排序后的数组 A 和 B，其中 A 的末端有足够的缓冲空间容纳 B。 编写一个方法，将 B 合并入 A 并排序。
     * 初始化 A 和 B 的元素数量分别为 m 和 n。
     * 示例:
     * 输入:
     * A = [1,2,3,0,0,0], m = 3
     * B = [2,5,6],       n = 3
     * 输出: [1,2,2,3,5,6]
     */
    public static void merge(int[] A, int m, int[] B, int n) {
        //思路：
        //因为A数组的后面总是0
        //则从A，B最后的一个“真实”元素开始对比
        //更大者放入A的最后面
        if (m == 0) {
            System.arraycopy(B, 0, A, 0, m + n);
            return;
        }
        int idx = m + n - 1;
        --n;
        m -= 1;
        while (m >= 0 && n >= 0) {
            if (A[m] >= B[n]) {
                A[idx--] = A[m--];
            } else {
                A[idx--] = B[n--];
            }
        }
        //由于总有一个数组先被移动完毕
        //若是A先被移动完毕，但B没有
        //则此时循环跳出，但B的元素并未完全添加到A中
        while (n >= 0) {
            A[idx--] = B[n--];
        }
    }
}














